Abstract: The hypergraph Moore bound is an elegant statement that characterizes the extremal trade-off between the girth (size of the smallest subhypergraph with all degrees even) and the number of hyperedges in a hypergraph. For graphs (i.e., 2-uniform hypergraphs), a bound tight up to the leading constant was proved in a classical work of Alon, Hoory and Linial. For hypergraphs of uniformity $k > 2$, an appropriate generalization was conjectured by Feige and resolved, up to an additional $\log^{4k+1} n$ factor in the size, in a recent work of Guruswami, Kothari and Manohar [GKM22], but their analysis, especially for the case of odd $k$, is significantly complicated. In this talk, I will present a substantially simpler and shorter proof of the hypergraph Moore bound, which also obtains tighter parameters. Our key idea is the use of a new reweighted Kikuchi matrix that allows us to drop several involved steps in GKM's analysis.
This is joint work with Pravesh K. Kothari and Sidhanth Mohanty.